package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 2020/12/31 下午6:57
 *
 * https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
 *
 *  判断一个树是否是平衡二叉树
 *
 *  如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
 */
public class _剑指Offer_55_II_平衡二叉树 {

    private static class TreeInfo{

        int deep;
        boolean isBalance;


        public TreeInfo(int deep, boolean isBalance) {
            this.deep = deep;
            this.isBalance = isBalance;
        }
    }

    public boolean isBalanced(TreeNode root) {

        if (root == null) {

            return true;
        }

        return isInBalanced(root).isBalance;
    }


    private TreeInfo isInBalanced(TreeNode treeNode) {

        if (treeNode == null) {

            return new TreeInfo(0,true);
        }

        TreeInfo leftTreeInfo = isInBalanced(treeNode.left);

        if (!leftTreeInfo.isBalance) {
            // 如果不是平衡二叉树，直接返回
            return new TreeInfo(0,false);
        }
        TreeInfo rightTreeInfo = isInBalanced(treeNode.right);

        if (!rightTreeInfo.isBalance || Math.abs(leftTreeInfo.deep - rightTreeInfo.deep) > 1) {

            return new TreeInfo(0,false);
        }

        return new TreeInfo(Math.max(leftTreeInfo.deep,rightTreeInfo.deep) + 1,true);
    }

}
